/*
 * @Author: your name
 * @Date: 2024-04-02 09:42:55
 * @LastEditTime: 2024-04-02 10:10:04
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\2810.故障键盘.cpp
 */
/*
 * @lc app=leetcode.cn id=2810 lang=cpp
 *
 * [2810] 故障键盘
 */

// @lc code=start
class Solution {
public:
    string finalString(string s) {
        deque<char> q;
        bool head = false;
        string ans;
        for(char chr:s){
            if(chr != 'i'){
                if(!head){
                    q.push_back(chr);
                }else{
                    q.push_front(chr);
                }
            }
            else{
                head = !head;
            }
        }
        ans = (head? string{q.rbegin(), q.rend()} : string{q.begin(), q.end()});
        return ans;
    }
};
// @lc code=end
/**
 比较直观的思路是我们实时维护答案字符串 ans\textit{ans}ans，当遇到非 “i”\text{``i''}“i” 的字符时，就将其加入字符串的末尾；否则将字符串进行反转。

然而字符串反转需要 O(l)O(l)O(l) 的时间，其中 lll 是当前 ans\textit{ans}ans 的长度，这样做的时间复杂度较高。事实上，当字符串进行反转后，在末尾添加字符等价于「不对字符串进行反转，并且在开头添加字符」。因此，我们可以使用一个双端队列和一个布尔变量 head\textit{head}head 来维护答案：

当遇到非 “i”\text{``i''}“i” 的字符时，如果 head\textit{head}head 为真，就在队列的开头添加字符，否则在队列的末尾添加字符；

当遇到 “i”\text{``i''}“i” 时，将 head\textit{head}head 取反。

head\textit{head}head 的初始值为假。这样一来，每一个字符只需要 O(1)O(1)O(1) 的时间进行处理。

当处理完所有的字符后，如果 head\textit{head}head 为真，那么将队列中的字符反序构造出答案字符串，否则正序构造出答案字符串。

作者：力扣官方题解
链接：https://leetcode.cn/problems/faulty-keyboard/solutions/2711922/gu-zhang-jian-pan-by-leetcode-solution-l9zg/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
